package reg_alloc;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;

import flow_graph.FlowGraph;
import graph.Node;
import temp.Temp;
import util.List;

public class Liveness extends InterferenceGraph
{
    private FlowGraph graph;
    
    public void addEdge(Node src, Node dst)
    {
        if ( src != dst && !dst.comesFrom(src) && !src.comesFrom(dst))
            super.addEdge(src, dst);
    }
    
    // estruturas usadas para computar a DFA
    private Hashtable<Node, HashSet<Temp>> in;
    private Hashtable<Node, HashSet<Temp>> out;
    private Hashtable<Node, HashSet<Temp>> gen;
    private Hashtable<Node, HashSet<Temp>> kill;
        
    public void show(PrintStream o)
    {       
        for ( List<Node> aux = this.nodes(); aux != null; aux = aux.tail )
        {
            Temp t = revMap.get(aux.head);
            
            o.print(t + ": [ ");
            for ( List<Node> adjs = aux.head.adj(); adjs != null; adjs = adjs.tail )
                o.print( revMap.get(adjs.head) + " ");
            o.println("]");
        }
    }
    
    // coisas uteis
    private MoveList moveList = null;
    
    private Hashtable<Node, Temp> revMap = new Hashtable<Node, Temp>();
    private Hashtable<Temp, Node> map = new Hashtable<Temp, Node>();
    
    public Liveness(FlowGraph g)
    {
        super();
    
        graph = g;
            
        computeGenKill();
        computeDFA();
        buildInterference();
    }

    public void dump(PrintStream outStream)
    {
    	graph.show(outStream);
    	
        int c=0;
        for(List<Node> aux = graph.nodes(); aux != null; aux = aux.tail, c++)
        {        	
            HashSet<Temp> i = in.get(aux.head);
            HashSet<Temp> o = out.get(aux.head);
            HashSet<Temp> g = gen.get(aux.head);
            HashSet<Temp> k = kill.get(aux.head);
            
            outStream.println(c+": gen:"+g+" kill:"+k+" in:"+i+" out:"+o);
        }
    }
    
    private void computeGenKill()
    {
        kill = new Hashtable<Node, HashSet<Temp>>();
        gen  = new Hashtable<Node, HashSet<Temp>>();
        
        for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
        {
            HashSet<Temp> k = new HashSet<Temp>();
            HashSet<Temp> g = new HashSet<Temp>();
            
            // kill
            for ( List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail )
                k.add(aux.head);
            
            // gen
            for ( List<Temp> aux = graph.use(nodes.head); aux != null; aux = aux.tail )
                g.add(aux.head);
            
            kill.put(nodes.head, k);
            gen.put(nodes.head, g);
        }
    }
    
    /**
     * 
     * @param a
     * @param b
     * @return true if a contains b
     */
    private boolean checkContains(HashSet<Temp> a, HashSet<Temp> b)
    {
    	for (Temp t : b)
    	{
    		if (!a.contains(t))
    			return false;
    	}

    	return true;
    }
    
    private boolean computeDFANodeIter(Node n)
    {
    	// out[n] = U in[filhos]
    	// in[n] = use[n] + (out[n] - def[n])
    	boolean changed;
    	    
    	HashSet<Temp> in = new HashSet<Temp>();
    	HashSet<Temp> out = new HashSet<Temp>();
    	HashSet<Temp> oldin = this.in.get(n);
    	HashSet<Temp> oldout = this.out.get(n);
    	HashSet<Temp> def = this.kill.get(n);
    	HashSet<Temp> use = this.gen.get(n);
    	 
    	// atualizamos out
    	// para cada sucessor de n 
    	for ( List<Node> l = n.succ(); l != null; l = l.tail )
    	{
    		Node s = l.head;
    		
    		HashSet<Temp> sin = this.in.get(s);
    		out.addAll(sin);
    	}
    	
    	// atualizamos in
    	in.addAll(use);
    	
    	// calcula (out[n] - def[n])
    	for(Temp t : out)
    	{
    		// para cada elemento em out
    		
    		// se o elemento nao está em def
    		if (!def.contains(t))
    			in.add(t); // entao sobrevive a diferenca dos conjuntos
    	}
    	
    	// verifica se houve mudanca
    	
    	// apenas tenta agilizar o processo no caso de haver mudanca obvia
    	if (in.size() != oldin.size() || out.size() != oldout.size())
    		changed = true;
    	else
    		changed = ! ( checkContains(in, oldin) && checkContains(oldin, in) && checkContains(out, oldout) && checkContains(oldout, out) );
    	
    	if (changed)
    	{
    		this.in.put(n, in);
    		this.out.put(n, out);
    	}
    	
    	return changed;
    }
       
    private void computeDFA()
    {
    	in = new Hashtable<Node, HashSet<Temp>>();
    	out = new Hashtable<Node, HashSet<Temp>>();
    	 
        List<Node> nodes = graph.nodes();
        java.util.LinkedList<Node> revNodes = new LinkedList<Node>();
        
        for ( List<Node> l = nodes; l != null; l = l.tail )
        {
        	in.put(l.head, new HashSet<Temp>());
        	out.put(l.head, new HashSet<Temp>());
        	
        	revNodes.addFirst(l.head);
        }
        
        boolean changed;
        
        do
        {
        	changed = false;
        	
	        for ( Node n : revNodes )
	        {
	        	changed = computeDFANodeIter(n) || changed;
	        }
        } while (changed);
        
        //dump(System.out);
    }
    
    private Node getNode(Temp t)
    {
        Node n = map.get(t);
        
        if ( n == null )
        {
            n = this.newNode();
            
            map.put(t, n);
            revMap.put(n, t);
        }
        
        return n;
    }
    
    private void handle(Node instr)
    {
        for( List<Temp> defs = graph.def(instr); defs != null; defs = defs.tail )
        {
            Node currentTemp = this.getNode(defs.head);
            
            for( Temp liveOut : out.get(instr) )
            {                
                Node currentLiveOut = this.getNode(liveOut);
                this.addEdge(currentTemp, currentLiveOut);
            }
        }
    }
    
    private void handleMove(Node instr)
    {
    	List<Temp> use = graph.use(instr);
    	
        Node dst = this.getNode(graph.def(instr).head);
        Node src = this.getNode(use.head);
        
        moveList = new MoveList(src, dst, moveList);
        
        for( Temp t : out.get(instr) )
        {
            Node currentOut = this.getNode(t);
            
            if ( currentOut != src )
            {
                //this.addEdge(currentOut, dst);
                this.addEdge(dst, currentOut);
            }
        }
    }
    
    private void buildInterference()
    {
        // Estamos sentados sobre ombros de um gigante...
        // Aqui, nos temos uma lista sobre todos os temporarios
        // vivos no fim de cada no. Desta forma, eh relativamente
        // facil construir a lista de adjacencia.
        
        for ( List<Node> instrs = graph.nodes(); instrs != null; instrs = instrs.tail )
        {
            Node current = instrs.head;
            
            if ( graph.isMove(current))
                handleMove(current);
            else
                handle(current);
        }
    }
    
    public Node tnode(Temp temp)
    {
        Node n = map.get(temp);
        
        if ( n == null )
        {
            map.put(temp, n = newNode() );
            revMap.put(n, temp);
        }
        
        return n;
    }

    public Temp gtemp(Node node)
    {
        return revMap.get(node);
    }

    public MoveList moves()
    {
        return moveList;
    }

    public HashSet<Temp> Out(Node node)
    {
        return out.get(node);
    }    
}
